Árbol de intervalo

En ciencia de la computación, un árbol de intervalo es una árbol ordenado para mantener intervalos. En concreto, permite encontrar de manera eficiente todos los intervalos que se solapan con cualquier otro intervalo o punto dado. A menudo se utiliza para las consultas de ventanas, por ejemplo, para encontrar todos los caminos en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el árbol de segmento.

La solución trivial es visitar cada intervalo y probar si se cruza el punto o intervalo dado, que requiere Θ(n) tiempo, donde n es el número de intervalos en la colección. Dado que una consulta puede devolver todos los intervalos, por ejemplo, si la consulta es un gran intervalo de intersección de todos los intervalos de la colección, esto es asintóticamente óptimo; Sin embargo, podemos mejorarlo al considerar algoritmos producto-sensible, donde el tiempo de ejecución se expresa en términos de m, el número de intervalos producidos por la consulta. Los Árboles de intervalo son dinámicos, es decir, que permiten la inserción y la supresión de intervalos. Obtienen un tiempo de consulta de O(log n), mientras que el tiempo de preprocesamiento para construir la estructura de datos es O(n log n) (pero el consumo de espacio es O(n)). Si los puntos extremos de los intervalos están dentro de un rango entero pequeño (por ejemplo, en el intervalo [1, ..., O (n)]), las estructuras de datos más rápidas existen con el tiempo de preprocesamiento O (n) y el tiempo de consulta O(1+m) para informar m intervalos que contienen un punto de consulta dada.

Enfoque Ingenuo

En un caso simple, los intervalos no se solapan y se pueden insertar en un simple árbol de búsqueda binario y consultar en O(log n) tiempo. Sin embargo, con intervalos arbitrariamente superpuestas, no hay manera de comparar dos intervalos para la inserción en el árbol desde ordenaciones según los puntos de inicio o los puntos finales pueden ser diferentes. Un enfoque ingenuo podría ser la construcción de dos árboles paralelos, uno ordenado por el punto de inicio, y el otro ordenado por el punto final de cada intervalo. Esto permite descartar la mitad de cada árbol en O(log n), pero los resultados se deben combinar, lo que requiere O(n) tiempo. Esto nos da consultas en O(n + log n) = O(n), que no es mejor que la fuerza bruta.

Los Árboles de Intervalo resuelven este problema. En este artículo se describen dos diseños alternativos para un árbol de intervalo, conocido como el árbol de intervalo centrado y el árbol aumentado.

Árbol de intervalo centrado

Las consultas requieren O(log n + m) tiempo, siendo n el número total de intervalos y siendo m el número de los resultados reportados. La construcción requiere O(n log n) tiempo, y el almacenamiento requiere O(n) el espacio.

Construcción

Dado un conjunto de n intervalos en la recta numérica, queremos construir una estructura de datos para que podamos recuperar de manera eficiente todos los intervalos superpuestos por otro intervalo o punto.

Comenzamos tomando toda la gama de todos los intervalos y dividiendo por la mitad en x_center (en la práctica, x_center deben ser recogidos para mantener el árbol relativamente equilibrado). Esto da tres conjuntos de intervalos, los que están completamente a la izquierda de x_center los llamaremos S_left, aquellos completamente a la derecha del x_center los llamaremos S_right, y aquellos que se superponen a x_center los llamaremos S_center.

Los intervalos en S_left y S_right se dividen de forma recursiva de la misma manera hasta que no haya intervalos a la izquierda.

Los intervalos que se solapan en S_center en el punto central se almacenan en una estructura de datos separada ligado al nodo en el árbol de intervalo. Esta estructura de datos se compone de dos listas, una que contiene todos los intervalos según sus puntos iniciales, y otra que contiene todos los intervalos según sus puntos finales.

El resultado es un árbol ternario con cada nodo de almacenamiento:

• Un punto central
• Un puntero a otro nodo que contiene todos los intervalos completamente a la izquierda del punto central
• Un puntero a otro nodo que contiene todos los intervalos completamente a la derecha del punto central
• Todos los intervalos que se superponen el punto central ordenados por su punto de comenzar
• Todos los intervalos que se superponen el punto central ordenados por su punto final

Intersección

Teniendo en cuenta la estructura de datos construida, recibimos consultas consisten en rangos o puntos, y retornamos todos los rangos en el conjunto original superponiendo esta entrada.

Con un punto

La tarea es encontrar todos los intervalos en el árbol que se superponen a un punto dado x. El árbol se recorre con un algoritmo recursivo similar al que se utiliza para atravesar un árbol binario tradicional.

Para cada nodo del árbol, x se compara con x_center, el punto medio utilizado en la construcción nodo anteriormente. Si x es menor que x_center, el conjunto de los intervalos de más a la izquierda, S_left, se considera. Si x es mayor que x_center, el conjunto de los intervalos de más a la derecha, S_right, se considera.

A medida que cada nodo se procesa a medida que atravesamos el árbol desde la raíz a una hoja, se procesan los rangos en su S_center. Si x es menor que x_center, sabemos que todos los intervalos en S_center terminan después de x, o no podrían también solaparse a x_center. Por lo tanto, sólo necesitamos encontrar esos intervalos en S_center que comienzan antes de x. Podemos consultar las listas de S_center que ya han sido construidas. Ya que sólo nos preocupamos por los inicios del intervalo en este escenario, se puede consultar la lista ordenada por comienzos. Supongamos que encontramos el número más cercano no mayor que x en esta lista. Todos los rangos desde el comienzo de la lista a la que se encuentra el punto de solapamiento x debido a que comienzan antes de x y finalizan después de x (tal como la conocemos, ya que se superponen en x_center que es mayor que x). Por lo tanto, podemos simplemente comenzar enumerando intervalos en la lista hasta que el valor del punto final supere a x.

Del mismo modo, si x es mayor que x_center, sabemos que todos los intervalos en S_center deben comenzar antes de x, por lo que nos encontramos con los intervalos que terminan después de x utilizando la lista ordenada por terminaciones de intervalos.

Si x coincide exactamente con x_center, todos los intervalos en S_center se pueden añadir a los resultados sin más trámite, el recorrido del árbol se puede detener.

Con un intervalo

En primer lugar, podemos reducir el caso a cuando un intervalo R se dado como entrada para el caso más simple, donde un solo punto se da como entrada. Hacemos esto primero mediante la búsqueda de todos los rangos en principio o puntos finales dentro del intervalo de entrada R utilizando un árbol construido por separado. En el caso de una sola dimensión, podemos usar un simple árbol que contiene todos los puntos iniciales y finales en el conjunto de intervalos, cada uno con un puntero a su intervalo correspondiente.

Una búsqueda binaria en O(log n) tiempo para el comienzo y el final de la R revela los puntos máximos y mínimos a considerar. Cada punto dentro de este rango hace referencia a un intervalo que se superpone a nuestra gama y se añade a la lista de resultados. Se debe tener cuidado para evitar duplicados, ya que un intervalo podría comenzar y terminar dentro de R. Esto se puede hacer usando una puntero binario en cada intervalo para marcar si es o no añadido al conjunto de resultados.

Los únicos intervalos aún no considerados son aquellos superpuestos a R que no tienen un punto final dentro de R, en otras palabras, los intervalos que lo encierran. Para encontrarlos, tomamos cualquier punto dentro de R y usamos el algoritmo de arriba para encontrar todos los intervalos de intersección de ese punto (de nuevo, teniendo cuidado de eliminar los duplicados).

Dimensiones Superiores

La estructura de datos de árbol de intervalos puede ser generalizada a una dimensión superior a N y tiempo de construcción y O(n log n) en espacio.

En primer lugar, un árbol de rango en N dimensiones está construido de manera que permite la recuperación eficiente de todos los intervalos con puntos iniciales y finales dentro de la región de consulta R. Una vez que se encuentran los rangos correspondientes, lo único que queda son esos rangos que encierran la región en alguna dimensión. Para encontrar estos solapamientos, se crean los árboles de intervalo N, y un eje de intersección R se consulta para cada uno. Por ejemplo, en dos dimensiones, la parte inferior de la plaza R (o cualquier otra línea horizontal de intersección R) se pueden consultar contra el árbol de intervalos construido para el eje horizontal. Del mismo modo, la izquierda (o cualquier otra línea vertical que se interseca con R) se pueden consultar contra el árbol de intervalos construido en el eje vertical.

Cada árbol de intervalos también necesita una adición de dimensiones superiores. En cada nodo que se recorre en el árbol, x se compara con S_center para encontrar solapamientos. En lugar de dos listas ordenadas de los puntos como se utilizó en el caso unidimensional, se construye un árbol de gama. Esto permite la recuperación eficiente de todos los puntos en que se superponen S_center región R.

Supresión

Si después de la eliminación de un intervalo desde el árbol, el nodo que contiene ese intervalo no contiene más intervalos, ese nodo puede ser eliminado del árbol. Esto es más complejo que una operación de eliminación en un árbol binario normal.

Un intervalo puede solapar el punto central de varios nodos en el árbol. Puesto que cada nodo almacena los intervalos que se solapan, con todos los intervalos completamente a la izquierda de su punto central en el subárbol izquierdo, de manera similar para el subárbol derecho, se sigue y cada intervalo se almacena en el nodo más cercano a la raíz del conjunto de nodos cuyo punto central se superpone.

Operaciones de eliminación normales en un árbol binario (para el caso en que el nodo se borre tiene dos hijos) implican la promoción de un nodo más de la raíz a la posición del nodo que se está eliminado (por lo general el hijo más a la izquierda del subárbol derecho, o el hijo más a la derecha del subárbol izquierdo).

Deleting a node with two children from a binary search tree using the in-order predecessor (rightmost node in the left subtree, labelled 6).

Como resultado de esta promoción, algunos nodos que estaban por encima del nodo promovido se convertirá en descendientes del mismo; es necesario buscar estos nodos para los intervalos que también se superponen el nodo promovido, y mover esos intervalos en el nodo promovido. Como consecuencia, esto puede dar lugar a nuevos nodos vacíos, los cuales deben ser eliminados, siguiendo el mismo algoritmo de nuevo.

Equilibrio

Las mismas cuestiones que afectan a la eliminación también afectan a las operaciones de rotación; la rotación debe preservar el invariante que los intervalos se almacenan tan cerca de la raíz como sea posible.

Árbol aumentado

Otra manera de representar intervalos se describe en Cormen et al. (2009, Section 14.3: Interval trees, pp. 348–354).

Tanto inserción y eliminación requieren O(log n), siendo n el número total de intervalos en el árbol antes de la operación de inserción o eliminación.

Utilice un árbol ordenado simple, por ejemplo, un árbol binario de búsqueda o árbol binario auto-equilibrio de búsqueda, donde el árbol se ordena por los valores "bajos" de los intervalos, y una anotación adicional es añadida a cada nodo del valor máximo en sus subárboles. Es fácil de obtener este atributo en sólo O (h) pasos durante cada adición o eliminación de un nodo, donde h es la altura del nodo añadido o eliminado en el árbol, mediante la actualización de todos los ancestros del nodo de abajo hacia arriba. Además, las rotaciones de los árboles usados durante la inserción y eliminación pueden requerir actualizar el alto valor de los nodos afectados.

Ahora, se sabe que dos intervalos A y B se superponen sólo cuando tanto A.Low ≤ B.High y A.High ≥ B.low. Al buscar en los árboles los nodos superpuestos con un intervalo dado, puede saltar de inmediato:

• todos los nodos a la derecha de nodos cuyo valor es bajo más allá del final del intervalo dado.
• todos los nodos que tienen su valor máximo por debajo del inicio del intervalo dado.

Un total del pedido se puede definir en los intervalos ordenándolas por primera vez por su valor 'bajo' y, finalmente, por su 'alto' valor. Esta ordenación puede ser usado para prevenir intervalos de duplicados de ser insertado en el árbol en O(log n) tiempo, en comparación con el O(k + log n) tiempo requerido para encontrar duplicados si los intervalos k se superponen en un nuevo intervalo.

Java Example: Adding a new interval to the tree

La llave de cada nodo es el intervalo en sí mismo, por eso cada nodo está ordenado primero por el menor valor y al final por el valo más alto, y el valor de cada nodo es el punto al final del intervalo:

 public void add(Interval i) {
     put(i, i.getEnd());
 }

Java Example: Searching a point or an interval in the tree

Para buscar un intervalo, caminas por el árbol, omitiendo las ramas que no contengan lo que estas buscando:

 // Search for all intervals which contain "p", starting with the
 // node "n" and adding matching intervals to the list "result"
 public void search(IntervalNode n, Point p, List<Interval> result) {
     // Don't search nodes that don't exist
     if (n == null)
         return;
 
     // If p is to the right of the rightmost point of any interval
     // in this node and all children, there won't be any matches.
     if (p.compareTo(n.getValue()) > 0)
         return;
 
     // Search left children
     if (n.getLeft() != null)
         search(IntervalNode (n.getLeft()), p, result);
 
     // Check this node
     if (n.getKey().contains(p))
         result.add(n.getKey());
 
     // If p is to the left of the start of this interval,
     // then it can't be in any child to the right.
     if (p.compareTo(n.getKey().getStart()) < 0)
         return;
 
     // Otherwise, search right children
     if (n.getRight() != null)
         search(IntervalNode (n.getRight()), p, result);
 }

where

a.compareTo(b) retorna un valor negativo si if a < b

a.compareTo(b) retorna 0 si a = b

a.compareTo(b) retorna un valor positivo si a > b

El código para buscar un intervalo es similar:

 // Check this node
 if (n.getKey().overlapsWith(i))
     result.add (n.getKey());

overlapsWith() is defined as:

 public boolean overlapsWith(Interval other) {
     return start.compareTo(other.getEnd()) <= 0 &&
            end.compareTo(other.getStart()) >= 0;
 }

Dimensión superior

Esto puede extenderse a dimensiones más altas por ciclos a través de las dimensiones en cada nivel del árbol. Por ejemplo, para dos dimensiones, los niveles impares del árbol pueden contener rangos para la coordenada x coordinate, mientras que los contienen incluso niveles rangos para la coordenada y coordinate. Sin embargo, no es bastante obvio cómo la lógica de rotación que tendrá ampliarse para mantener el árbol balanceado.

Una solución mucho más simple es utilizar árboles de intervalos anidados. En primer lugar, crear un árbol utilizando los rangos para y coordinate. Ahora, para cada nodo en el árbol, añadir otro árbol de intervalos en los rangos de x , para todos los elementos cuyo rango y  se interseca con ese nodo en y .

La ventaja de esta solución es que se puede extender a una cantidad arbitraria de dimensiones utilizando la misma base de código.

Al principio, el costo de los árboles adicionales podría parecer prohibitivo, pero que por lo general no es el caso. Al igual que con la solución anterior, es necesario un nodo por x coordinate, por lo que este costo es el mismo en ambas soluciones. La única diferencia es que se necesita una estructura de árbol adicional por intervalo vertical. Esta estructura es típicamente muy pequeña (un puntero al nodo raíz más tal vez el número de nodos y la altura del árbol).

• Datos: Q6057306